﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows;
using theeg.GraphWpf.Models;

namespace theeg.GraphWpf.Arrangement
{
    public class Layered : IArrangement
    {
        protected readonly Dictionary<INode, NodeArrangementData> ArrangementData = new Dictionary<INode, NodeArrangementData>();

        protected List<INode>[] Layers;

        private List<INode> _nodes = new List<INode>();
        protected readonly HashSet<INode> DummyNodes = new HashSet<INode>();
        protected readonly List<Transition> RemovedTransitions = new List<Transition>();
        protected readonly List<Transition> InvertedTransitions = new List<Transition>();
        private readonly double _marginX;
        private readonly double _marginY;
        private readonly bool _horizontal;
        private readonly IGraph _graph;

        public Layered(IGraph graph, double marginX, double marginY, bool horizontal)
        {
            _graph = graph;
            _marginY = marginY;
            _marginX = marginX;
            _horizontal = horizontal;
        }

        protected void BuildArrangementData()
        {
            _nodes = _graph.Nodes.ToList();
            ArrangementData.Clear();
            int index = 0;
            foreach (var node in _nodes)
            {
                ArrangementData[node] = new NodeArrangementData { GenericCounter = index++ };
            }
        }

        public void Arrange()
        {
            BuildArrangementData();
            if (_nodes.Count == 0)
            {
                return;
            }

            RemoveControlPoints();

            RemoveCycles();
            if (RemoveTransitiveEdges)
            {
                RemoveTransitiveEdgesAction();
            }
            AssignLayersLongestPath();
            RestoreCycles();
            IntroduceDummyNodes();
            ReduceCrossings();
            FlushPositions();
            ConvertDummyNodesToControlPoints();
        }

        private void RemoveTransitiveEdgesAction()
        {
            var toRemove = new List<Transition>();
            foreach (var data in _nodes.Where(x => x.OutgoingEdges.Count == 0))
            {
                var currentPath = new Stack<INode>();

                RemoveTransitiveEdgesRecursive(data, currentPath, toRemove);
            }
            foreach (var transition in toRemove)
            {
                var target = transition.Target;
                var source = transition.Source;
                target.IncomingEdges.Remove(transition);
                source.OutgoingEdges.Remove(transition);
                _graph.Transitions.Remove(transition);
            }
        }

        private void RemoveTransitiveEdgesRecursive(INode target, Stack<INode> currentPath, IList<Transition> toRemove)
        {
            if (currentPath.Contains(target))
            {
                return;
            }
            if (currentPath.Count > 0)
            {
                var peek = currentPath.Peek();
                for (int index = target.OutgoingEdges.Count - 1; index > -1; index--)
                {
                    var transition = target.OutgoingEdges[index];
                    if (transition.Target == peek)
                    {
                        continue;
                    }
                    if (currentPath.Contains(transition.Target))
                    {
                        toRemove.Add(transition);
                    }
                }
            }
            currentPath.Push(target);
            foreach (var transition in target.IncomingEdges)
            {
                RemoveTransitiveEdgesRecursive(transition.Source, currentPath, toRemove);
            }
            currentPath.Pop();
        }

        public bool RemoveTransitiveEdges { get; set; }

        private void RemoveControlPoints()
        {
            var transitions = _graph.Transitions.ToList();
            foreach (var transition in transitions)
            {
                transition.ClearControlPoints();
            }
        }

        /// <summary>
        /// breadth first traversal
        /// mark (visited transitions) and (nodes where all afferences have been visited)
        /// remove, when there already is another edge between the two nodes
        /// invert the edge, when visiting an already marked node
        /// </summary>
        protected void RemoveCycles()
        {
            var visitedEdges = new HashSet<string>();
            var visitedNodes = new HashSet<int>();
            var routesToProcess = new Queue<INode[]>();
            var springs = _nodes.Where(x => x.IncomingEdges.Count == 0);

            foreach (var node in springs)
            {
                routesToProcess.Enqueue(new[] { node });
            }
            if (routesToProcess.Count == 0)
            {
                routesToProcess.Enqueue(new[] { _nodes[0] });
            }
            while (visitedNodes.Count < ArrangementData.Count)
            {
                while (routesToProcess.Count > 0)
                {
                    var route = routesToProcess.Dequeue();
                    var node = route[route.Length - 1];
                    var source = ArrangementData[node];
                    for (int index = 0; index < node.OutgoingEdges.Count; index++)
                    {
                        var outgoing = node.OutgoingEdges[index];
                        var target = ArrangementData[outgoing.Target];
                        if (route.Contains(outgoing.Target))
                        {
                            if (visitedEdges.Contains(source.GenericCounter + "x" + target.GenericCounter) ||
                                visitedEdges.Contains(target.GenericCounter + "x" + source.GenericCounter))
                            {
                                RemovedTransitions.Add(outgoing);
                                node.OutgoingEdges.RemoveAt(index);
                                outgoing.Target.IncomingEdges.Remove(outgoing);
                                index--;
                            }
                            else
                            {
                                InvertedTransitions.Add(outgoing);
                                outgoing.SetConnection(outgoing.Target, node);
                                index--;
                            }
                        }
                        else
                        {
                            visitedEdges.Add(source.GenericCounter + "x" + target.GenericCounter);
                            var newRoute = new INode[route.Length + 1];
                            Array.Copy(route, newRoute, route.Length);
                            newRoute[route.Length] = outgoing.Target;
                            routesToProcess.Enqueue(newRoute);
                        }
                    }
                    visitedNodes.Add(source.GenericCounter);
                }
                if (visitedNodes.Count < ArrangementData.Count)
                {
                    var notProcessed = ArrangementData.First(x => !visitedNodes.Contains(x.Value.GenericCounter));
                    routesToProcess.Enqueue(new[] { notProcessed.Key });
                }
            }
        }

        protected void AssignLayersLongestPath()
        {
            foreach (var data in ArrangementData.Where(x => x.Key.OutgoingEdges.Count == 0))
            {
                foreach (var incomingEdge in data.Key.IncomingEdges)
                {
                    AssignNewLayer(incomingEdge.Source, 0);
                }
            }

            ShrinkLayerDepth();

            int maxLayer = 0;
            foreach (var data in ArrangementData)
            {
                maxLayer = Math.Max(maxLayer, (int)data.Value.Y + 1);
            }
            Layers = new List<INode>[maxLayer];
            for (int i = 0; i < Layers.Length; i++)
            {
                Layers[i] = new List<INode>();
            }
            foreach (var data in ArrangementData)
            {
                var layerIndex = maxLayer - 1 - (int)data.Value.Y;
                data.Value.Y = layerIndex;
                var layer = Layers[layerIndex];
                layer.Add(data.Key);
                data.Value.X = layer.Count;
            }
        }

        private void ShrinkLayerDepth()
        {
            foreach (var data in ArrangementData)
            {
                double minDepth = double.MaxValue;
                foreach (var incomingEdge in data.Key.IncomingEdges)
                {
                    var depth = ArrangementData[incomingEdge.Source].Y;
                    minDepth = Math.Min(minDepth, depth);
                }
                if (Math.Abs(minDepth - double.MaxValue) > double.Epsilon)
                {
                    data.Value.Y = Math.Max(data.Value.Y, minDepth - 1);
                }
            }
        }

        private void AssignNewLayer(INode target, int layer)
        {
            var arrangementData = ArrangementData[target];
            if (layer >= arrangementData.Y && layer <= _nodes.Count)
            {
                arrangementData.Y = layer + 1;
                foreach (var transition in target.IncomingEdges)
                {
                    AssignNewLayer(transition.Source, layer + 1);
                }
            }
        }

        protected void IntroduceDummyNodes()
        {
            DummyNodes.Clear();
            foreach (var node in _nodes)
            {
                var source = ArrangementData[node];
                foreach (var outgoing in node.OutgoingEdges.ToList())
                {
                    var target = ArrangementData[outgoing.Target];
                    if (Math.Abs(source.Y - target.Y) <= 1) continue;
                    AddDummiesForTransition(outgoing, source, target);
                }
            }
        }

        private void AddDummiesForTransition(Transition original, NodeArrangementData source, NodeArrangementData target)
        {
            INode currentNode = original.Source;
            var targetNode = original.Target;
            Transition currentTransition = original;
            if (source.Y < target.Y)
            {
                for (double i = source.Y + 1; i < target.Y; i++)
                {
                    var dummy = new Node { Width = 0, Height = 0 };
                    var arrangementData = new NodeArrangementData
                    {
                        X = target.X,
                        Y = i
                    };
                    ArrangementData.Add(dummy, arrangementData);
                    DummyNodes.Add(dummy);
                    currentTransition.SetConnection(currentNode, dummy);
                    currentTransition = new Transition();
                    currentNode = dummy;
                    Layers[(int)i].Add(dummy);
                }
                currentTransition.SetConnection(currentNode, targetNode);
            }
            else
            {
                for (double i = source.Y - 1; i > target.Y; i--)
                {
                    var dummy = new Node { Width = 0, Height = 0 };
                    var arrangementData = new NodeArrangementData
                    {
                        X = source.X,
                        Y = i
                    };
                    ArrangementData.Add(dummy, arrangementData);
                    DummyNodes.Add(dummy);
                    currentTransition.SetConnection(currentNode, dummy);
                    currentTransition = new Transition();
                    currentNode = dummy;
                    Layers[(int)i].Add(dummy);
                }
                currentTransition.SetConnection(currentNode, targetNode);
            }
        }

        protected void ReduceCrossings()
        {
            var random = new Random(1);
            for (int pass = 0; pass < 10; pass++)
            {
                foreach (var node in _nodes.Union(DummyNodes).OrderBy(x => random.Next()))
                {
                    var outgoingCount = node.OutgoingEdges.Count;
                    var incomingCount = node.IncomingEdges.Count;
                    var count = outgoingCount + incomingCount;
                    if (count == 0) continue;
                    //barycenter
                    double center = 0;
                    foreach (var transition in node.OutgoingEdges)
                    {
                        var target = ArrangementData[transition.Target];
                        center += target.X;
                    }
                    foreach (var transition in node.IncomingEdges)
                    {
                        var source = ArrangementData[transition.Source];
                        center += source.X;
                    }
                    center = center / count;
                    ArrangementData[node].X = center;
                }
                StraightenDummyEdges();
                AssignSlots();
            }

            StraightenDummyEdges();
        }

        private void StraightenDummyEdges()
        {
            var occupiedSlots = new HashSet<Point>();
            foreach (var node in _nodes)
            {
                var arrangement = ArrangementData[node];
                occupiedSlots.Add(new Point(arrangement.X, arrangement.Y));
            }

            var lastDummies = from x in DummyNodes where !DummyNodes.Contains(x.OutgoingEdges[0].Target) select x;
            foreach (var endNode in lastDummies)
            {
                var x = ArrangementData[endNode.OutgoingEdges[0].Target].X;
                var currentNode = endNode;
                while (DummyNodes.Contains(currentNode))
                {
                    var arrangement = ArrangementData[currentNode];
                    if (!occupiedSlots.Contains(new Point(x, arrangement.Y)))
                    {
                        arrangement.X = x;
                    }
                    x = arrangement.X;
                    currentNode = currentNode.IncomingEdges[0].Source;
                }
            }
        }

        private void AssignSlots()
        {
            foreach (var layer in Layers)
            {
                var sorted = layer.OrderBy(x => ArrangementData[x].X).ToList();
                layer.Clear();
                layer.AddRange(sorted);
                int medianIndex = layer.Count / 2;
                if (medianIndex == -1)
                {
                    medianIndex = layer.Count;
                }

                double nextSlot = Math.Floor(ArrangementData[layer[medianIndex]].X) + 1;
                double nextDummySlot = Math.Floor(ArrangementData[layer[medianIndex]].X) + 1;
                for (int index = medianIndex; index < layer.Count; index++)
                {
                    var node = layer[index];
                    var nextNode = layer[Math.Min(index + 1, layer.Count - 1)];
                    var isDummy = DummyNodes.Contains(node) || DummyNodes.Contains(nextNode);
                    var nodeArrangementData = ArrangementData[node];
                    nodeArrangementData.X = Math.Max(Math.Ceiling(nodeArrangementData.X), isDummy ? nextDummySlot : nextSlot);
                    nextSlot = Math.Max(Math.Ceiling(nodeArrangementData.X + 1), nextSlot + 2);
                    nextDummySlot = Math.Max(Math.Ceiling(nodeArrangementData.X + (isDummy ? 0 : 1)), nextSlot + (isDummy ? 0 : 2));
                }
                nextSlot = Math.Floor(ArrangementData[layer[medianIndex]].X);
                for (int index = medianIndex - 1; index > -1; index--)
                {
                    var node = layer[index];
                    var nextNode = layer[Math.Max(index - 1, 0)];
                    var isDummy = DummyNodes.Contains(node) || DummyNodes.Contains(nextNode);
                    var nodeArrangementData = ArrangementData[node];
                    nodeArrangementData.X = Math.Min(Math.Floor(nodeArrangementData.X), isDummy ? nextDummySlot : nextSlot);
                    nextSlot = Math.Min(Math.Floor(nodeArrangementData.X - 1), nextSlot - 2);
                    nextDummySlot = Math.Min(Math.Floor(nodeArrangementData.X - (isDummy ? 0 : 1)), nextSlot - (isDummy ? 0 : 2));
                }
            }
        }

        protected void ConvertDummyNodesToControlPoints()
        {
            //TODO controlpoints currently for bezier, not suitable for straight
            var firstDummies = (from x in DummyNodes where !DummyNodes.Contains(x.IncomingEdges[0].Source) select x).ToArray();
            foreach (var route in firstDummies)
            {
                INode currentNode = route;
                var incomingEdge = currentNode.IncomingEdges[0];
                var source = incomingEdge.Source;
                INode lastNode = source;
                while (DummyNodes.Contains(currentNode))
                {
                    var outgoingEdge = currentNode.OutgoingEdges[0];
                    var target = outgoingEdge.Target;
                    target.IncomingEdges.Remove(outgoingEdge);

                    incomingEdge.SetConnection(source, target);
                    if (_horizontal)
                    {
                        var margin = _marginX * 0.5;
                        var isforward = lastNode.Left < currentNode.Left;
                        var x = isforward ? lastNode.Left + lastNode.Width + margin : lastNode.Left - margin;
                        if (Math.Abs(lastNode.Top - currentNode.Top) > double.Epsilon)
                        {
                            var x1 = isforward ? x - margin : x;
                            incomingEdge.AddControlPoint(new Point(x1, currentNode.CenterY + (lastNode.CenterY - currentNode.CenterY) * 0.9));
                        }
                        int sign = isforward ? 1 : -1;
                        incomingEdge.AddControlPoint(new Point(x, currentNode.CenterY + (lastNode.CenterY - currentNode.CenterY) * 0.1));
                        incomingEdge.AddControlPoint(new Point(x + sign * (currentNode.Width - margin), currentNode.CenterY));
                        incomingEdge.AddControlPoint(new Point(x + sign * 2 * (currentNode.Width - margin), currentNode.CenterY));
                    }
                    else
                    {
                        var margin = _marginY * 0.5;
                        var isforward = lastNode.Top < currentNode.Top;
                        var y = isforward ? lastNode.Top + lastNode.Height + margin : lastNode.Top - margin;
                        if (Math.Abs(lastNode.Left - currentNode.Left) > double.Epsilon)
                        {
                            var y1 = isforward ? y - margin : y;
                            incomingEdge.AddControlPoint(new Point(currentNode.CenterX + (lastNode.CenterX - currentNode.CenterX) * 0.9, y1));
                        }
                        int sign = isforward ? 1 : -1;
                        incomingEdge.AddControlPoint(new Point(currentNode.CenterX + (lastNode.CenterX - currentNode.CenterX) * 0.1, y));
                        incomingEdge.AddControlPoint(new Point(currentNode.CenterX, y + sign * (currentNode.Height - margin)));
                        incomingEdge.AddControlPoint(new Point(currentNode.CenterX, y + sign * 2 * (currentNode.Height - margin)));
                    }
                    lastNode = currentNode;
                    currentNode = currentNode.OutgoingEdges[0].Target;
                    ArrangementData.Remove(currentNode);
                }
                if (lastNode != null)
                {
                    if (_horizontal)
                    {
                        var x = lastNode.Left < currentNode.Left
                            ? currentNode.Left - _marginX
                            : currentNode.Left + currentNode.Width + _marginX;
                        incomingEdge.AddControlPoint(new Point(x, lastNode.CenterY));
                    }
                    else
                    {
                        var y = lastNode.Top < currentNode.Top
                            ? currentNode.Top - _marginY
                            : currentNode.Top + currentNode.Height + _marginY;
                        incomingEdge.AddControlPoint(new Point(lastNode.CenterX, y));
                    }
                }
            }

            DummyNodes.Clear();
        }

        protected void RestoreCycles()
        {
            foreach (var transition in RemovedTransitions)
            {
                transition.Source.OutgoingEdges.Add(transition);
                transition.Target.IncomingEdges.Add(transition);
            }
            RemovedTransitions.Clear();
            foreach (var transition in InvertedTransitions)
            {
                InvertTransition(transition);
            }
            InvertedTransitions.Clear();
        }

        private static void InvertTransition(Transition transition)
        {
            var source = transition.Source;
            var target = transition.Target;
            transition.SetConnection(target, source);
        }

        protected void FlushPositions()
        {
            var columnCenter = new Dictionary<int, double>();
            var layerCenter = new Dictionary<int, double>();
            var columnOffset = new Dictionary<int, double>();
            var layerOffset = new Dictionary<int, double>();
            foreach (var pair in ArrangementData)
            {
                var node = pair.Key;
                var arrangement = pair.Value;
                var width = _horizontal ? node.Height : node.Width;
                var height = _horizontal ? node.Width : node.Height;

                columnCenter[(int)arrangement.X] = columnCenter.ContainsKey((int)arrangement.X) ? Math.Max(columnCenter[(int)arrangement.X], width) : width;
                layerCenter[(int)arrangement.Y] = layerCenter.ContainsKey((int)arrangement.Y) ? Math.Max(layerCenter[(int)arrangement.Y], height) : height;
            }
            double sum = 0;
            foreach (var column in columnCenter.OrderBy(x => x.Key).ToArray())
            {
                columnOffset[column.Key] = sum;
                sum = sum + column.Value + _marginX;
                columnCenter[column.Key] = sum - (column.Value + _marginX) * 0.5;
            }
            sum = 0;
            foreach (var row in layerCenter.OrderBy(x => x.Key).ToArray())
            {
                layerOffset[row.Key] = sum;
                sum = sum + row.Value + _marginY;
                layerCenter[row.Key] = sum - (row.Value + _marginY) * 0.5;
            }
            foreach (var pair in ArrangementData)
            {
                var node = pair.Key;
                bool isDummy = DummyNodes.Contains(node);
                var arrangement = pair.Value;
                if (_horizontal)
                {
                    node.Left = layerCenter[(int)arrangement.Y] - (isDummy ? 0 : node.Width * 0.5);
                    node.Top = columnCenter[(int)arrangement.X] - (isDummy ? 0 : node.Height * 0.5);
                    if (isDummy)
                    {
                        node.Width = layerCenter[(int)arrangement.Y] - layerOffset[(int)arrangement.Y];
                    }
                }
                else
                {
                    node.Left = columnCenter[(int)arrangement.X] - (isDummy ? 0 : node.Width * 0.5);
                    node.Top = layerCenter[(int)arrangement.Y] - (isDummy ? 0 : node.Height * 0.5);
                    if (isDummy)
                    {
                        node.Height = layerCenter[(int)arrangement.Y] - layerOffset[(int)arrangement.Y];
                    }
                }
            }
        }
    }
}
